"""This module contains functions which are shared by the majority of the 
modules within this library.
""" 

"""Project Euler Solutions Library

Copyright (c) 2011 by Robert Vella - robert.r.h.vella@gmail.com

Permission is hereby granted, free of charge, to any person obtaining a copy
of this software and associated documentation files (the "Software"), to deal
in the Software without restriction, including without limitation the rights
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
copies of the Software, and to permit persons to whom the Software is
furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in
all copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
THE SOFTWARE.
"""


def infinity(start = 0, step = 1):
    """Generates an infinite range starting from [start] and adding [step]
    each time.
    """
     
    current_number = start
    
    while True:    
        yield current_number
        current_number += step
         
def isinteger(n): 
    """Returns true if [n] is an integer or a truncated float."""
    return int(n) == n

def whichinteger(n):        
    """Returns [n] if [n] is an integer or a truncated float. Otherwise 
    this function returns None.
    """
    
    proved = isinteger(n)
    
    if proved:
        return int(n)
    else:
        return None
    
class LazyEvaluatedList:
    """A procedural list which caches those results it generates. Derivatives of
    this class can be used as an efficient abstract representation of an 
    infinite set, such as the set of primes or the set of fibonacci numbers.
    
    When a result for a particular index is requested (such as the nth prime)
    this class will calculate the result at that index and all indexes that 
    came before it, and store them for future use. If the result has already
    been calculated, it will return it instead.
    
    New infinite lists can be created by inheriting this class and implementing
    the method, _next_item, which should return the next number based on the 
    last result in the series -- which is passed to the method, along with the 
    number of known terms.
    """
        
    def __init__(self, known_terms, precal = 0):
        """Parameters: 
        
        known_terms - The terms which are already known for this list.
        precal - The number for which all terms below it will be calculated.
        """
        self._replace_known_terms(known_terms)
        
        if precal != 0:
            self._precalculate(precal)        
    
    def __getitem__(self, desired_index):
        #Calculate all the terms up to and including the [desired_index]th 
        #term.
        if desired_index >= self._number_of_known_terms:
            for n in range(self._number_of_known_terms, desired_index + 1):
                next_item = self._next_item(self._known_terms[-1],
                                           self._number_of_known_terms 
                                           )
                
                self._known_terms.append(next_item)
                self._innerset.add(next_item)
                self._number_of_known_terms += 1
        
        #Return the [desired_index]th term.
        return self._known_terms[desired_index] 

    def terms(self):
        """Returns an unordered set object with all the unique terms in this 
        list.
        """
        
        return self._innerset        
        
    def _next_item(self, last_result, number_of_known_terms):
        """Returns the next item in the sequence. 
        
        Parameters:
            last_result - The last term evaluate before this one.
            number_of_known_terms - The number of terms which have been 
                                calculated.
            
        Note: 
            This method should be implemented by inheritors of this class.
        """
        
        raise NotImplementedError    
        
    def _precalculate(self, precal):
        """Precalculates and stores all the terms <= [precal]."""
        
        for i in infinity(self._number_of_known_terms):
            if self[i] > precal:
                break
            
    def _replace_known_terms(self, newterms):
        """Replaces all the known terms with [newterms]."""
        
        self._known_terms = newterms
        
        self._innerset = set(newterms) 
        self._number_of_known_terms = len(newterms)  
           

            
